package com.leetcode.LC_MED;

import java.util.*;

public class LC102 {
    public List<List<Integer>> levelOrder(TreeNode root) {//BFS

        ArrayList<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (queue.size() != 0) {
            int size = queue.size();//当前层有多少元素
            ArrayList<Integer> list1 = new ArrayList<>();
            while (size != 0) {
                TreeNode nodeTmp = queue.poll();
                list1.add(nodeTmp.val);
                if (nodeTmp.left != null) {
                    queue.add(nodeTmp.left);
                }
                if (nodeTmp.right != null) {
                    queue.add(nodeTmp.right);
                }
                size--;
            }
            list.add(new ArrayList<>(list1));
        }
        return list;
    }

    // **********************************************************************

    public List<List<Integer>> levelOrder2(TreeNode root) {//DFS

        ArrayList<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        dfs(root, list, 0);

        Collections.reverse(list);//反转
        return list;
    }

    private void dfs(TreeNode node, List<List<Integer>> list, int level) {

        if (node==null){
            return;
        }
        if (level>list.size()-1){
            list.add(new ArrayList<>());
        }
        list.get(level).add(node.val);
        if (node.left!=null){
            dfs(node.left,list,level+1);
        }
        if (node.right!=null){
            dfs(node.right,list,level+1);
        }
    }
}
